/*
1、题目：1943. 描述绘画结果：https://leetcode.cn/problems/describe-the-painting/
2、标签：哈希，前缀和，排序
3、思路： 
        1、哈希单位化，区间值
        2、转化成升序数组，保证按数轴方式连续
        3、求前缀和，求出重叠区间的值的中和
        4、根据前缀和为0，说明区间不存在，来生成res区间
*/
class Solution {
public:
    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
        unordered_map<int, long long> unit;
        for(auto it : segments){
            int l = it[0];
            int r = it[1];
            int val = it[2];
            if(!unit.count(l)){
                unit[l] = 0;
            }
            unit[l] += val;
            if(!unit.count(r)){
                unit[r] = 0;
            }
            unit[r] -= val;        
        }
         
        //2、转化成升序数组
        vector<pair<int, long long>> vec;
        for(auto it : unit){
            vec.emplace_back(it.first, it.second);
        }
        sort(vec.begin(), vec.end());

        //3、求前缀和
        int vec_len = vec.size();
        for(int i = 1; i < vec_len;i++){
            vec[i].second += vec[i-1].second;
        }
        
        //4、生成区间
        //  vector<vector<long long>> res;
        //  for(int i = 0; i < vec_len - 1; i++){
        //     if(vec[i].second != 0){
        //         res.emplace_back(vector<long long>{vec[i].first, vec[i+1].first, vec[i].second});
        //     }
        //  }
               vector<vector<long long>> res;
         for(int i = 1; i < vec_len; i++){
            if(vec[i-1].second != 0){
                res.emplace_back(vector<long long>{vec[i-1].first, vec[i].first, vec[i-1].second});
            }
         }
         return res;
    }
};